# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/15 上午10:22
    Author  : Thinkgamer
    File    : 665-非递减数列.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/non-decreasing-array/
"""
"""
给你一个长度为n的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的：对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明：
1 <= n <= 10 ^ 4
- 10 ^ 5<= nums[i] <= 10 ^ 5
"""

"""
	v1: 去掉一个元素，判断剩下的是否是非递减序列
		提交运行超时
	v2: 扫描一遍即可
		如果 数据元素个数小于等于2，直接返回true
		修改前两个元素为有序，因为是非递减，所以要保证前边的数尽可能的小，比较前两个数，如果第一个比第二个大，则修改第一个元素值为第二个元素值
		从第一个元素开始遍历，如果当前元素 > 下一个元素，需要判断左侧值和右侧值的关系
			如果left > right，因为遵循尽可能小原则，应该修改右侧值为 当前值
			其他：修改当前值为左侧值
"""


def check_possibility_v1(nums):
	# 去掉某元素后，剩下的是非递减序列的个数
	for i in range(len(nums)):
		new_nums = nums[0:i] + nums[i+1:len(nums)]
		# 判断去掉nums[i] 之后是否是非递减序列
		flag = True
		for j in range(len(new_nums)-1):
			if new_nums[j] > new_nums[j+1]:
				flag = False
		if flag:
			return True
	return False


def check_possibility_v2(nums):
	# 记录需要移除的元素数
	changeCount = 0
	
	# 如果nums的个数小于等于2，肯定是可以的
	if len(nums) <= 2:
		return True
	
	# 保证前两个有序，为了保证非递减，应保证前边的数 小一些
	if nums[1] < nums[0]:
		changeCount += 1
		nums[0] = nums[1]
		
	for i in range(1, len(nums)-1):
		right = nums[i+1]
		if nums[i] > right:  # 说明需要改变一个数，无论改变哪一个数
			changeCount += 1
			if changeCount > 1:  # 如果需要改变二个及以上的数，说明不满足条件，需要停止
				return False
			
			# 判断需要改变哪一个数
			left = nums[i-1]
			if left > right:
				nums[i+1] = nums[i]
			else:
				nums[i] = left
	return True


# nums = [1]
# nums = [4, 2, 3]
#nums = [4, 2, 1]
# nums = [3, 4, 2, 3]
# nums = [-1, 4, 2, 3]
# nums = [5, 7, 1, 8]
nums = [1,6922,4713,6615,750,3244,1685,2624,4439,5523,5803,8416,5460,336,1593,9714,42,1373,3353,3169,4253,5462,4520,1851,774,7618,2664,7415,9627,391,2383,9280,5255,5694,7426,3620,2064,5751,8279,2656,2715,991,352,3110,3806,7349,4955,6974,4643,1841,6892,754,6260,8505,7236,6168,8478,5455,9203,3334,9864,4621,56,2263,6004,5833,1151,9351,2775,8241,1341,2504,1837,8997,8294,6381,3886,692,9758,6691,5294,7761,1733,2774,1461,1236,276,7833,108,909,7421,3248,9330,6109,7815,3016,1591,6290,7303,2285,5969,1848,386,6571,9290,2034,7350,7478,8099,10,160,5323,1420,9369,656,3880,9107,2299,208,2888,3385,5016,4554,262,3788,3817,9105,2065,2647,9623,3679,5417,3855,6081,9207,7473,2342,8513,3709,9255,6551,5820,5185,9576,7539,7407,3102,8006,7553,7792,332,4660,9110,7342,4567,7481,9003,9621,7298,2981,3148,8222,7442,3582,3183,5954,8584,7998,4632,8441,5350,254,9260,1573,2284,5094,3377,1165,6578,7709,9042,1556,8868,4641,1884,2811,1402,3482,7026,6282,7468,8925,5355,5851,2772,3199,9634,1011,6883,726,2661,8909,8190,766,1509,5832,5636,444,2615,7949,1875,1004,4652,2010,4410,3134,3551,4389,3487,4768,7763,8859,5623,8035,8813,381,3274,5192,2380,3258,1456,2212,6427,339,3685,3718,4268,6035,7513,220,1711,6300,9976,2159,2898,1902,6647,2452,1824,8450,2021,2940,7771,7136,1320,1937,5485,3660,1745,34,8039,9889,8598,4143,4999,6821,1647,6949,2853,5816,3872,7352,7477,3645,9908,615,4380,4953,5641,9354,793,6854,2178,1770,8078,2268,1028,5418,1115,8926,3637,4415,7185,1031,1999,1576,3362,1583,9876,2592,5258,4121,5919,4914,8939,4430,148,3378,4997,731,8901,8113,6125,5857,1796,2792,4272,1792,5374,3733,8132,6512,1391,7739,6238,6486,9671,3836,554,3750,501,4503,6465,3909,6853,3839,1081,1143,9142,3100,8462,8382,2717,3475,1405,9707,7256,9763,676,3821,5991,9215,2493,1636,4009,776,4445,4497,8212,7151,1888,8043,6955,6204,1328,3792,8977,9157,5456,1124,8972,1502,6727,4145,5198,1854,2621,976,54,1842,2625,8454,5483,9407,8487,7378,9210,1261,6746,7020,6773,5059,6518,7069,2759,9888,2651,6706,8321,4438,8668,5928,3753,1231,7495,5222,4036,7251,6429,2935,6391,3382,5253,6710,1056,3759,9834,1964,8768,9604,1905,1423,4758,810,6408,6388,2385,117,5688,9939,6786,85,5972,6537,512,7115,9599,9449,5713,8556,5801,2733,5388,8083,9459,6640,8271,3492,9637,6806,190,1823,5819,5033,4679,4097,4855,2357,5425,5320,5441,3215,5982,8131,1613,1417,1571,7749,9691,7458,6749,3068,2635,2139,7615,2690,2307,345,8756,1893,4000,3731,60,5861,4391,8989,5121,3307,1386,8956,861,9200,6341,3978,8771,2215,343,2858,2924,29,5755,1827,4681,928,7977,9423,1407,8724,1246,6476,1419,50,2121,9974,752,2234,5548,6190,2749,8522,6591,8621,5951,5371,613,2830,3643,1126,3171,2528,312,9570,8980,490,1857,2414,7552,457,5506,4005,7893,8295,5804,6641,9755,5572,4337,9433,3160,5575,3965,5842,9825,3577,3038,8000,683,1592,6791,5352,7512,3757,9334,8683,7699,9655,8159,5340,8469,6446,7383,3041,2346,9830,7290,3871,2042,498,1988,8874,1539,9086,1730,5552,269,5672,3622,6328,2408,1144,3609,805,1431,7954,5180,6301,474,6181,4104,3997,3889,6516,6521,9585,7920,3257,6830,7666,1323,563,9674,8452,5629,4553,4722,7724,1801,1300,8306,9005,379,450,5167,2510,2202,7339,9416,4659,8163,5532,8208,5151,570,7328,4922,2327,1447,3508,9759,7438,8263,8912,2194,2331,8392,4122,727,2641,9398,5159,6855,8276,7313,239,8201,890,4373,9514,402,8195,7141,2429,4791,5502,1707,7410,8265,6374,6508,8317,72,7359,5764,7604,9895,8900,4871,4168,8164,1786,6287,1315,1516,723,9360,2189,4511,235,6587,7841,3598,4692,5042,6645,4792,8816,9325,8614,9871,4935,8033,6458,9052,9248,5438,2292,1646,7878,2209,4463,7454,3608,2332,8895,9901,3397,625,7496,3060,7872,1650,3242,5886,3652,5655,1228,47,4332,2371,4517,4397,3052,3437,5048,524,951,6179,3542,6277,4806,264,4051,1337,171,8057,1180,1832,3815,1219,8993,7988,4728,5014,3320,699,2995,7608,5624,1709,3050,2679,2512,371,8063,4499,7280,2314,6787,7281,6775,5287,8451,3357,1973,8703,4215,103,576,2241,632,1975,6823,177,6474,4237,9656,4140,6194,4374,2049,9150,5341,6193,4940,7487,9884,2610,1424,2271,7531,162,4939,7622,1790,8561,8070,1995,1171,1160,3031,3177,6272,3000,6711,7610,3246,6261,1532,5353,9062,5646,3596,3506,4770,7482,5452,7424,84,1482,4452,3208,378,1135,8430,8714,3489,3644,7066,7736,7455,6015,7505,4316,6188,5484,3864,946,9880,5847,16,682,7698,3575,9512,8341,528,8011,9004,7099,7983,1314,7682,1335,8205,5749,5366,6284,8298,3105,3781,2453,4642,7591,4173,3343,4510,2542,4034,6042,7268,8116,611,9178,1319,1830,4973,5527,9641,5279,7634,8435,725,6400,9665,1080,4244,3984,875,109,1175,5158,5061,2716,2497,6909,768,3681,3153,3989,1157,7616,5123,8937,8860,1068,646,6344,992,448,8479,1474,1430,6659,8472,4406,6961,6191,6793,8251,8605,3715,9439,6198,6019,2944,9515,4516,6398,5476,2726,1332,1968,1759,2796,7032,5387,8375,3404,4639,6140,8834,1618,9584,3931,2894,4777,2998,4440,8244,3720,877,9381,9931,9209,6824,8847,4533,1392,5130,1787,2620,6233,2954,7863,6994,3138,9575,2247,427,1523,8149,7167,461,1896,3070,6060,1397,5525,2709,9845,5099,8172,3162,8434,4963,9693,703,7607,6827,9061,8403,3649,7196,4591,404,3534,5923,2699,9361,7299,1079,145,1810,1484,6502,5770,4263,5331,4209,3066,9324,1992,1577,1676,521,7486,2770,170,3458,2052,4525,8551,5498,2735,589,4019,5257,6900,88,6431,7226,6251,3304,7409,878,8499,6426,8408,6887,9535,7810,2784,4583,4863,8258,3470,1890,8003,7330,3627,1105,4328,5419,5569,5513,9044,9698,5461,8599,8907,6704,7657,5914,8415,8021,92,3425,6842,6963,9119,6088,6367,5879,4824,2056,3830,1663,6472,500,9638,2238,2376,7835,7098,7790,2459,5858,8710,4465,309,3789,1023,5464,8436,6936,1503,2718,5657,5983,2297,8555,3793,5735,2354,30,7704,7850,8248,3027,8067,8942,8896,9944,4453,3688,7137,3592,4286,7002,4996,5090,3887,4742,4090,9687,3865,4245,8955,3214,824,4158,8012,6173,4826,8908,2110,2412,5766,8036,5814,8468,2687,2266,5473,8811,7688,4909,6337,9737,6053,7788,7063,7474,8424,3161,9798,5745,8566,9809,2534,3390,5741,3194,3885,1250,8442,579,5026,715,1024,2277,975,477,3779,3247,2062,1791,4089,7555,7244,3841,9567,8444,8185,2746,7877,7204,5798,9473,9152,8066,8765,3387,6007,5233,8832,3588,9149,4669,5303,3835,8232,871,4293,3870,2890,7541,3046,3625,1748,5288,2713,9166,9746,2574,2200,471,2382,8455,1807,3711,7985,8308,4075,6276,8330,9214,8141,2947,7527,9524,2880,1043,6050,8918,9467,3682,4483,3945,5152,4620,5432,9540,4491,324,3695,4280,481,9561,9289,9263,2691,8196,7695,7404,6720,1864,6062,5579,2519,5276,9733,2827,6132,1805,7955,8662,5472,4745,7288,3960,8289,8304,166,1322,6880,3053,3572,7772,629,2819,863,5178,6471,1582,6295,1184,9179,6650,7435,6406,2016,5116,2017,6671,8720,9743,9716,5239,1005,8485,6294,4040,1195,5429,4473,3968,4512,5018,9411,8560,9573,2551,5074,8697,7959,4819,2491,3619,9130,2258,4096,2301,3518,137,1363,2879,1620,5056,9919,9136,9109,7172,557,9594,8198,9221,1563,7230,3727,3265,363,4832,7131,355,5584,6864,8611,4984,6745,3008,4437,1358,6907,5040,3347,5097,8806,301,7755,8219,8582,4271,1369,3948,1485,2876,1691,5612,6914,3332,6220,77,9768,2856,1033,8974,6368,3062,6418,4971,4291,8256,8930,253,6935,9680,8397,6269,1720,5526,8315,977,7738,9878,4318,7088,862,3842,5673,9987,4734,5964,708,2213,44,8122,4299,685,483,5077,9116,6380,4504,368,1510,8199,6962,4342,4868,4776,104,3696,879,4631,9686,3369,831,4747,7547,1036,4214,8526,7543,9749,743,6595,4561,5683,7630,506,4800,5662,1045,843,6376,281,9206,8722,2561,8971,2570,5644,983,3574,6459,9009,8512,1062,5559,6164,1316,1550,8585,515,3373,9448,1445,1765,7276,9541,6090,5022,3858,5876,1406,2689,9756,6162,8706,6189,3591,6298,6868,4837,6584,4619,2118,5805,5273,6394,3486,5635,4297,8985,1093,4270,7283,4604,3903,5934,3420,2962,820,3543,213,7248,9769,7705,9988,4042,4847,4918,1285,2415,3114,2594,5590,8486,387,7500,8153,4848,1330,1897,7837,6765,2196,7003,38,8915,9802,80,8553,3074,8092,5686,8510,7848,8020,5465,5703,5369,8220,7400,5051,8023,3295,3760,5127,2760,9124,4766,841,6941,1467,5561,4883,12,5068,2702,6373,6483,5072,4024,2375,8776,2054,7374,5426,6986,7189,6894,2745,8748,4873,3231,4623,5992,3090,2144,9218,4638,1173,7387,9481,2765,9926,6481,6948,4802,4148,1371,1538,5978,9400,9734,4248,5434,6297,4805,5073,7277,9811,5028,5702,8970,6910,466,7546,4117,8953,7201,1439,3468,1215,9572,9961,3964,9453,2068,5975,5219,9379,7043,6308,9921,4531,8941,9016,4565,8015,5550,3150,8537,434,407,4182,6627,7613,6976,5809,7804,5989,8852,9090,4106,6724,2996,5175,660,6413,9000,4240,5773,4296,6016,1238,7981,9148,5378,7523,4916,9188,3129,7867,1149,7703,2517,3179,2207,9810,3670,3082,6536,7016,4814,3350,957,2955,4607,3126,286,2302,7028,289,2374,5453,8936,8145,9427,668,1492,5503,9305,3488,6533,3163,9947,738,9918,9465,530,1586,2460,3530,5003,6979,6543,5280,7008,6758,193,9012,9848,2368,6588,8028,1598,4235,4436,969,9724,4,4738,6392,408,6395,7053,9968,3936,3337,2783,5176,1614,6668,900,1621,9349,756,5585,8182,8849,3804,5881,5002,6658,1669,4064,8818,4184,7309,1483,2515,4408,9430,229,9887,4804,3273,8752,7191,3328,4155,6302,5038,414,3267,3703,5013,236,8194,4730,4633,7889,1629,5509,6275,1027,5640,388,1861,5538,5405,5979,2147,8829,2677,8293,5083,4177,419,1774,9955,1958,5883,5782,2433,8636,4224,5880,3764,6556,8760,182,5986,8062,1401,582,4070,3034,7046,7340,4361,4098,2136,3198,3212,3663,2556,4103,3152,2695,5965,1139,6637,2721,3629,6265,737,9659,8678,2840,981,9775,9292,7064,1396,3174,9025,441,1641,4888,4954,2039,7807,7970,997,6237,6723,2389,6106,3354,2554,1954,1943,859,3938,1789,6436,5041,3595,1037,6970,5742,1611,6066,2432,4657,9328,7582,5993,9023,9027,51,9640,3222,4858,1408,8651,985,8268,2725,1076,204,7802,7992,4087,8565,1433,7894,1270,61,2541,5020,5148,1724,9393,292,2442,6924,5377,6712,7520,8873,8973,8277,8521,4509,2009,1524,2985,7492,2320,7219,8085,6522,3234,1535,4211,1297,8882,1956,4119,4981,7953,9606,2631,5787,8596,9513,496,125,9291,3868,9424,9269,9699,3853,1252,7361,1898,6801,8437,7193,9017,9710,1071,8948,4115,9923,6568,4362,250,3547,1637,2347,7517,1696,1233,6363,7642,2424,2916,8089,2113,837,2029,4575,3048,5941,4818,3098,3389,7106,2511,2922,6104,6925,9718,5075,616,8511,891,5445,8234,7259,669,4231,1987,1230,2197,216,3498,6000,353,932,7680,6714,9796,2337,4564,2242,3063,7958,9835,5430,2507,1978,6506,3807,6135,5987,3783,7493,1276,7733,3276,8188,1512,2595,4887,4260,8911,6681,3381,5396,6447,7362,3957,1458,1984,7502,4157,8284,5717,7491,260,4204,5496,4451,8707,3593,5147,2303,2309,9712,6399,3256,244,2579,6074,5322,6468,8799,1395,5916,473,6496,6383,13,9418,7759,2448,5034,1247,9057,2711,2315,4487,2804,4850,8569,4513,6372,7497,8577,9365,3075,9662,6223,7398,5998,2003,1951,4603,5894,1412,3785,9673,2820,4677,1860,9080,7116,5957,3910,2290,1870,5399,4421,2220,9229,6932,865,7757,3943,3137,7646,8741,6170,152,2938,1527,6488,2190,5700,5400,3191,9438,4107,8583,8810,8531,385,354,8209,2124,6675,7427,28,8817,3290,6701,9161,8218,9902,6748,9670,5443,8792,9236,1183,4570,6159,4349,3120,617,5795,2015,5960,6958,8231,3309,8733,9318,8564,4407,6985,7120,8843,7195,5603,6917,4049,247,5587,4708,9694,3471,5290,6430,6582,3358,225,7190,2590,5272,7952,3505,4968,7345,7785,2137,2096,5697,2402,7324,5491,1715,5163,8180,8986,7655,1980,3655,7930,3597,3092,7777,27,8494,2546,1788,8762,9622,5740,4484,3125,5202,161,4581,2997,1442,8782,201,9883,6689,113,1672,4627,3443,4108,3180,8660,4870,9730,3338,1156,2558,2100,3929,9509,9950,9256,5490,400,978,6565,2471,5300,5017,7847,7765,3940,2904,8136,3813,2537,1348,9376,2480,7372,790,4556,5206,4052,3226,1272,2923,5079,1829,9965,6933,4671,1844,7870,6923,2111,7293,7535,4859,4134,2191,9613,6988,313,3687,1682,1521,1794,5010,2602,8590,523,1608,609,9404,8965,6006,4044,8539,7798,9231,4403,4443,3391,1894,6443,2388,9493,8079,8291,3308,2692,9723,3741,8837,9551,614,2712,9164,5224,203,364,1428,2122,8270,5200,4624,8203,681,6639,8946,7934,4461,8842,2073,1828,3892,4694,6743,2022,2377,5784,3845,7701,7612,9682,8045,278,300,4314,333,5166,3901,8383,2087,9340,3227,1129,1835,6848,6992,1213,5890,9181,3998,18,936,1486,4527,1610,6834,3927,9619,898,9543,1077,6250,516,529,6736,6182,319,9392,6055,6487,3795,4906,2934,3571,5095,484,7275,4664,9296,7292,7085,2423,5507,1915,8870,5466,3850,6266,9451,5263,8108,3926,6107,9197,7117,8229,20,5663,8366,9313,5853,7903,8593,7528,8458,5515,2179,539,266,9553,724,3787,2167,3747,6694,8213,6419,7408,7039,2166,6180,5398,9934,4282,9645,7114,4840,8377,8119,9307,8966,6783,642,6770,1560,6021,4382,9286,1277,7584,9525,5114,7865,291,8249,5736,5759,5935,9409,5783,7571,5138,8346,4498,9434,2078,3664,2747,7304,6013,6126,6018,9098,520,3782,2130,2060,7180,8688,8428,3537,1122,4540,5284,6146,2181,1327,4256,8146,8402,9914,9587,7928,4275,2224,8607,7286,1422,5693,2359,1850,2925,4969,2815,751,5232,6357,3264,1211,8207,5829,6199,3003,6881,1345,9175,9963,8924,3272,482,9824,3185,6314,1110,6245,6865,6114,417,8492,2514,3986,7693,1273,7673,4811,947,2929,5659,5499,4978,6402,3678,6805,7025,9458,9106,6014,6136,7416,3690,9593,2619,307,3096,3325,1398,7012,9501,4739,9299,2539,8056,105,7393,7034,633,1411,2917,1776,5593,6973,7562,7597,347,8496,4900,5221,9629,7072,9067,2464,4335,952,5981,420,157,499,7000,3908,8514,4137,8951,5712,6482,7279,9413,8861,6507,8684,3562,7602,8875,7070,2205,7720,6167,2564,5734,4135,6759,6141,2013,7907,3532,4128,5488,3473,321,4028,3326,9472,5543,3319,4927,8945,827,1480,9643,641,6154,1493,817,7644,5743,4799,1708,8694,6542,8671,5827,9550,7830,9728,8144,9605,4428,6987,3766,8691,4682,4249,5129,2522,7811,494,2502,9180,7182,694,7843,591,2279,8283,1264,781,2852,6989,6098,7588,9006,5946,67,2142,4329,9250,9977,158,6008,9498,518,1020,7247,8396,5594,6023,5156,6555,9577,4775,7568,5608,7791,2581,2070,1268,1060,4596,6001,5168,4129,4697,1648,6285,2903,8325,460,9079,3576,3549,9470,4420,9153,6674,9320,7391,1044,7729,1354,4897,7756,1513,9667,7599,1259,3121,8772,6309,2500,3303,3972,9672,426,6781,2229,3118,227,5882,1633,4751,1569,2278,4615,8934,7910,5818,3262,9917,6386,2928,4674,5531,2164,6594,6733,346,6024,9752,958,3146,9272,8546,4331,1178,4808,8126,5413,5902,4489,176,9018,5860,1092,4393,273,8176,6660,3005,5510,9065,8047,7860,5519,7200,1589,3051,9261,2201,4974,5321,3922,5122,3345,9455,1921,7049,4228,7329,5862,195,4539,9940,5649,1435,8506,6163,1267,549,9690,8835,6044,5004,7228,8106,9170,826,3310,2482,360,8238,9853,3195,3730,3554,4736,3216,5402,4932,8580,509,4780,1063,5390,3819,8780,839,2694,5758,7740,2024,3423,4820,2455,5849,3395,6819,4720,4188,8600,8050,3778,9387,5036,7911,8183,9284,118,4379,6657,5630,6975,5153,5286,1562,2378,5522,9800,3621,2580,8438,3740,5679,7564,4702,7882,2609,9011,5007,3628,4226,9056,3131,5332,3860,1704,4022,5598,2535,5684,2243,2942,757,7214,1706,7684,702,7570,7234,3746,2485,8147,2794,5071,8592,1533,2045,7231,1764,7586,9804,5812,9695,9504,1699,5039,8374,1766,9412,2675,1665,7764,7360,5628,2044,3589,3436,121,3411,5011,3202,4246,1910,8737,398,9886,8336,3882,772,1204,1846,940,106,8932,532,7912,3296,6553,7254,8757,1872,5535,1667,6010,3483,1262,9428,3777,8013,2730,2910,9614,2095,7609,6058,1972,7242,2126,4385,3744,2162,9899,4823,3599,6369,1255,9002,8419,624,2795,4007,256,2366,2887,3122,9571,622,1324,1913,9549,9654,6666,503,1977,7260,3578,6338,7814,6348,1185,7479,1220,7471,562,2468,6828,4743,2769,8681,4946,3607,9925,3368,3004,2973,5576,5346,9831,9251,4786,1946,6886,7080,5917,7010,3545,7083,5716,156,3271,5487,9315,5259,7140,3824,8191,7927,6755,3786,4651,1935,8464,7825,8947,3352,2645,2107,4352,3712,857,3221,6882,3869,9117,7556,3466,3406,4756,7660,2789,1381,459,3042,1260,6928,856,901,7653,6148,9015,6655,9789,7819,5199,9675,2878,5930,3025,4563,102,3080,5737,2727,2288,5045,4911,1912,4767,5333,7042,8235,6606,6352,5511,4913,8633,5533,7081,4345,7606,9317,4041,4788,4398,5489,7932,6246,9432,9882,1840,4589,8493,2336,3376,1868,8410,205,995,164,1511,2680,3259,2093,2317,8579,3279,1899,5475,5361,2117,7125,4216,3918,9932,4945,9405,9347,1096,4425,7923,4727,7343,8789,6829,2014,1017,214,3283,7526,9399,3826,3181,6112,5298,3963,1761,9279,2236,2959,8115,7842,4600,2031,4432,248,1179,1751,6930,6467,8778,5437,8933,5431,3427,3014,9020,7973,8060,2458,1781,3970,9007,687,2465,7184,1578,3317,695,8629,4704,1464,2983,6089,6612,4724,972,8338,8504,697,6075,7436,8574,4232,513,3516,6726,3493,1867,1619,1990,7143,3144,802,1284,5838,3987,1210,3030,2780,3079,3843,2306,2608,8483,1594,5440,305,9854,4726,3951,942,4856,2885,4546,1957,4610,2386,9457,2896,7348,4725,2411,7714,1695,9230,3563,1561,2591,1891,7048,6213,5566,2153,8280,9402,2407,8303,9484,6340,1712,9442,773,4588,7341,9173,4845,7294,9302,3372,3973,7576,7826,2206,2293,1283,2920,693,8791,9676,7119,3907,4037,689,9316,3934,6076,1242,5674,6067,9420,3525,5132,4154,5135,5225,9912,2286,7170,4842,2199,4388,3371,847,2131,7087,9858,675,5730,9391,3859,4923,6788,3187,7549,1189,1380,1965,8840,650,6841,1372,5223,7466,5887,458,4030,3751,696,7440,6692,5984,2119,7255,6371,1376,2372,7780,8355,1540,8567,6094,8626,9281,210,4526,1002,5031,1010,138,1295,7575,6905,2659,4608,2280,4189,8290,6680,6166,2077,9155,4283,8267,4571,2187,4300,9616,3955,2198,1732,5850,2850,261,8624,1266,9096,5821,9041,5364,5435,8689,189,6776,6490,2418,1064,739,7105,6039,5126,905,7198,6501,9994,1303,4920,5266,5451,9114,2496,1256,4153,684,7371,2767,6643,7173,7220,8609,6942,288,7869,8224,672,8118,2566,7879,7101,9554,8964,3897,631,4353,3178,6299,783,4162,8516,5407,6530,3370,4360,1114,4082,9185,7419,9474,3706,4424,6423,7974,4508,59,4175,4180,2966,8890,7991,380,2932,8536,3155,3445,7199,8264,9055,5560,7162,1820,3106,3780,314,6583,76,5748,6713,2980,5112,4210,8501,8400,3421,5208,7133,6271,8963,1030,4648,4091,8509,5105,1347,1047,7719,6079,5096,6915,3995,4961,4903,2822,4288,8189,8161,5101,2176,6410,963,652,4481,4457,778,6289,8071,1488,5269,8998,4789,308,1863,7033,3528,6678,9390,4630,6515,3294,2018,5586,2518,7795,7405,4198,6215,7124,1359,7504,1865,4723,8649,2048,9738,9933,2169,8693,1153,6576,4442,866,4928,1497,6096,4545,2616,9174,4910,40,1147,8919,3719,178,8331,116,1089,6764,7854,3361,2409,7950,7301,4262,9495,1769,6221,4303,6780,5852,2319,1725,7206,9008,1370,7713,8823,5477,9583,6303,2216,46,1947,6331,6353,7394,8525,623,8743,4057,3151,9612,6214,5571,6321,3422,3646,3875,2463,864,1249,9466,3933,2071,5171,78,5606,573,7058,7781,5070,2350,3019,1871,2345,5638,8761,8439,1849,600,6421,6011,6,545,9819,7741,3939,4234,1649,9964,6891,7593,4524,9460,8540,2684,9866,303,7691,3932,9841,2810,5891,2255,6065,4635,7598,9892,6235,9356,3878,2688,3581,8784,4139,6778,7091,2264,7130,2404,1040,413,8370,2803,9580,9339,2865,9353,2012,5826,8545,9953,3245,6229,1073,849,9942,604,9791,3568,8929,8696,8287,3967,2600,8644,5469,945,2392,5246,2063,120,9471,6980,6991,2499,6769,6600,6698,9669,874,3992,2606,3065,7735,3281,6097,2806,3641,6547,6326,5904,7516,4952,4344,6322,5395,7700,2958,5719,2782,1541,988,984,5779,9454,3961,6982,705,3238,5291,8215,14,5481,7846,1361,5968,6573,8098,7272,8630,5414,9822,868,8349,4851,7885,8243,9068,7311,2335,6513,2329,3344,411,8380,455,5204,4371,4212,3541,4265,5607,956,5501,3912,2214,4458,8005,4404,536,2204,1927,1500,4414,9808,1240,8064,1602,2627,1615,8034,5415,6837,4276,9765,2230,1443,5911,1174,5752,410,9348,8446,8210,154,6937,9425,5177,796,9440,1740,5872,7940,3023,5433,436,4112,8461,1225,4195,4320,9075,5967,8386,1931,8457,844,2105,4105,964,3250,9771,3018,2824,2150,1806,5134,2086,1374,326,2477,2907,6574,4875,5231,7880,9385,1998,4304,7157,5289,2492,2430,3852,4127,6876,9685,807,4957,6283,2251,3158,3538,3117,5021,4719,8529,7766,5835,1291,6709,6939,5468,2703,560,2091,1209,8645,6495,9120,2444,5397,1942,3457,5032,1310,5600,8858,4307,7975,8822,8888,4949,1454,8631,7465,6738,2844,2961,8595,7107,4938,2231,2565,2714,6836,4586,4056,7249,3426,3827,4447,9720,4534,8615,1007,6218,194,3485,6683,1895,5145,5459,8659,7082,4466,3157,5124,2160,4544,8520,86,4050,7004,688,4790,8038,5856,7620,2779,3799,9681,8476,207,3925,6048,5836,1645,7662,4321,1148,8184,7645,7331,3409,9445,5794,7412,2362,4551,3496,3176,3913,4217,5631,8568,5582,206,7445,5342,9877,7587,7453,2520,4941,2919,8723,634,1752,6211,5172,7875,2563,8394,7334,1834,6370,1199,9792,9742,2723,6810,3550,979,3418,6652,8739,7459,87,7029,5354,7056,9879,8406,722,4026,6061,7238,8404,2957,1568,6345,5937,2731,4306,1966,548,7262,2304,2978,3336,37,6895,101,700,9126,1078,147,4865,2112,4803,1117,9823,1494,4663,6835,3798,6603,3061,277,4613,4919,5019,1734,4595,6273,2614,2369,5467,4907,7722,2676,7548,7957,1542,3511,7573,6911,6679,1198,7148,7267,4706,9053,6478,1940,1876,4223,8785,357,5810,3624,2428,6815,8266,8502,9159,6753,5542,2569,7045,5379,7717,7452,36,3991,2710,8109,9990,403,2397,6012,5698,5203,2634,6644,5212,2148,9867,1996,514,8320,913,2836,9486,4926,4831,924,4193,1049,3047,2440,915,1920,9074,6031,8881,2742,8528,3091,7960,1075,4612,2751,4003,2132,7658,7779,1269,7112,2108,8202,9162,8613,4796,9259,1469,151,5924,7351,3974,259,4584,5822,17,3260,5054,679,4687,4869,2218,914,5589,3154,9916,8729,836,1351,493,9364,5087,8173,9198,6327,2343,7514,4593,8100,7834,8827,6131,2203,9323,7239,2182,3946,3474,4164,3396,8542,5052,376,2918,3615,1701,8893,804,127,5551,7302,8252,3107,6715,6741,4934,3088,2282,1200,9863,2669,8102,7821,7320,8848,4083,3497,9024,1191,9954,9903,7617,6539,246,7964,2982,83,9684,7775,2523,854,8728,786,6138,9807,1248,140,1717,7252,415,7635,3024,8367,607,8708,2454,7808,3240,7179,2023,8467,8820,5899,7718,5547,3697,4094,4367,8247,2598,4144,5601,9523,9983,8282,6147,5067,791,3200,310,9805,8352,4101,1627,7323,1253,5945,4229,4537,9770,7754,6445,9101,4470,4931,4085,9123,8240,5634,845,2613,5169,7902,3557,8969,8699,6799,8482,3341,3094,8543,3476,8059,9355,315,911,5652,2605,7444,9446,9697,422,1982,6602,129,8186,6768,1365,4550,3586,759,8508,4006,8316,2531,3055,1588,9456,1760,3758,9,6407,2649,5154,822,4817,9122,1182,8150,1101,5747,7422,1214,8931,3944,4166,1318,1125,5164,8357,5939,3286,8082,6999,7569,2812,9814,3398,7040,1048,588,456,760,3893,8313,2758,4341,3952,8421,3010,5230,3603,480,3626,7509,7982,1959,8223,3802,2936,5190,3510,6412,3400,8692,9071,4989,2098,6661,3552,2262,8072,9843,4628,6916,9818,5771,2571,7532,7488,4351,1908,3001,2274,3883,1082,4327,249,4230,9639,4334,2930,1353,8667,4308,5401,3770,5670,541,1504,5846,5913,6983,6995,2992,1859,8426,8603,8552,6203,1387,1819,9047,3736,5555,5125,3099,3983,8376,7122,5098,8738,7871,4908,2719,5480,8344,9945,4102,5228,8311,9190,186,7050,5229,237,2473,6253,9492,9344,4701,3546,3011,3223,9708,5528,7793,8094,3205,4392,9410,9488,439,2457,6870,6517,621,9773,5194,4807,131,2901,581,2082,8337,4656,4259,1039,5958,8559,6209,5927,5790,9794,711,6611,8166,8591,2989,6313,1,2835,6288,1839,2503,1983,6934,8051,561,7916,9099,2027,2312,5573,4515,959,8767,406,4377,7461,5292,6306,4784,1172,5884,3324,510,5421,5420,1212,7001,9709,4541,9022,5557,3315,9228,7726,4446,1762,7786,7305,4298,5933,5210,5520,4668,9371,6831,9715,2406,3009,4290,8628,6305,7978,7915,6171,8090,7831,8715,1917,9813,6669,3490,6620,4680,7519,651,1678,2902,5104,2808,5626,9838,6545,3930,1989,4343,6526,8807,519,918,3769,1815,7178,1605,2161,1755,9396,7853,9422,1022,8952,3141,3168,8809,3694,595,885,5265,9054,2443,6664,3590,1499,9595,9443,6084,7750,9195,3461,9359,5596,1154,7938,7129,3503,6346,4156,8324,6981,4993,3790,5254,4956,6708,4690,351,8705,2449,5595,4395,5427,5084,9132,183,7031,452,3464,8049,3077,6564,5120,1331,2786,1190,9536,9436,6256,7336,6361,2663,437,4529,2662,188,8701,2697,1961,9744,806,2650,2365,5179,1003,6254,1014,2088,470,2800,3966,2732,504,1450,8550,2552,1601,4683,9657,7169,9647,3284,9144,6921,8019,8962,4018,6784,4435,4058,6358,8307,9574,2848,6366,9094,8471,594,382,1640,3749,180,8775,1929,5359,4206,6844,7823,9980,5215,6580,2870,4081,7769,3999,6174,1383,7221,6717,2809,222,1607,5750,4958,8417,747,3032,4213,9388,3143,2766,1385,9115,3469,8431,6152,9797,1974,1816,9176,9496,7783,505,9960,5029,3228,3956,2949,1753,1674,6889,3891,1546,9389,2419,4255,7097,1360,9582,819,9444,8286,962,7621,4864,5687,1658,1223,6025,4717,3691,7753,1032,4912,181,4578,2632,1131,5139,6274,1979,639,4536,7211,3044,1021,2829,4147,3614,8547,1531,4196,146,5558,9874,6124,3159,6846,3639,6613,97,8518,4038,9581,475,5616,4471,2261,5076,5720,3816,328,4684,8237,9869,7380,5896,2975,2479,7963,7962,3459,1997,3448,6393,3412,8242,3220,6896,6310,5871,659,5227,7055,4753,1941,3737,1000,6200,2226,8841,1378,1780,9527,1142,5877,7317,6347,1449,6622,4787,1280,9267,2862,5863,7052,9285,7212,7656,2360,8398,5423,8133,1425,1293,4794,5588,2498,5714,2217,1163,6737,2089,3288,9542,3270,5494,7594,2877,7782,1091,5157,7906,1192,5448,1690,2753,9978,4560,1793,2646,7392,9633,1229,9530,2330,4319,5844,2351,7075,3775,6003,7054,7686,8892,5196,65,4695,6411,6499,7976,6226,8880,3359,5329,6439,7824,2294,1926,1292,6638,8226,3313,4194,8796,2041,198,5907,2143,4330,4750,7273,6567,4076,5143,1222,1525,3558,8721,4815,1055,5530,5690,1653,9982,9915,3673,2970,6069,8233,2813,3113,7227,297,3323,8663,707,6461,6761,673,6020,4061,5226,9288,1642,6248,1086,5870,9329,6403,218,8,338,2435,3698,7443,1657,3209,8857,4667,6735,7972,5334,927,356,1967,798,1134,9073,9450,7908,6177,3355,2681,9836,8302,572,1095,8656,6030,7965,4592,4281,3916,8236,3958,6866,8634,8751,9332,5637,1763,3213,8362,8449,115,6604,6550,5250,6702,185,4647,9213,1012,2494,9063,5564,1522,5721,1155,3026,6610,7891,3109,2899,6879,132,8961,2587,5047,3977,2488,119,3327,3020,9386,5319,3705,5344,2478,5915,7827,1235,6722,1585,7521,6425,9429,3812,6756,93,840,8808,1099,4384,8828,7250,325,5654,7628,1355,2305,930,7883,4093,5327,1399,5754,2969,7306,1460,5035,3128,7246,263,6045,4943,6143,9192,8923,7353,4376,8711,8594,3774,7319,279,3818,9345,4450,4160,9764,4782,1470,7933,8027,5903,8014,3451,8165,5785,7222,8214,674,533,9310,6498,3441,9856,5768,375,1662,9776,6292,5633,6466,2028,2211,209,9617,6977,5541,9311,9891,5627,416,3844,2180,3,586,9559,3058,8387,2700,5372,4754,9894,8661,6790,2744,1590,383,8134,9046,8657,2927,3976,8301,5824,5859,1549,8128,9851,5128,3569,9127,5470,1390,3529,5763,5909,9972,8443,6957,2582,196,3635,1057,257,9701,5760,894,3953,8327,3479,1128,7574,2232,491,5973,4519,8648,3763,9104,5160,9861,1668,3439,787,3564,5618,789,9678,9137,6820,5889,567,8718,7126,5109,7480,2281,980,8869,9294,2797,6389,1909,8616,1916,4241,8453,1501,8604,7559,7702,172,159,4434,3822,5920,6440,6677,5786,9700,451,3484,6579,7996,9070,7567,11,3906,6570,9201,492,9927,1087,4495,7332,6703,8503,4590,6589,2866,2787,8411,5367,2267,9658,1168,970,8673,8314,7218,2173,7257,7447,3584,3745,4640,486,6469,8745,1181,2470,6480,7382,8670,5037,9679,3707,7758,3794,9082,1660,4990,5900,4063,7675,3732,6807,2588,350,7358,9491,7385,126,6063,1670,9984,7947,540,1311,5706,2729,7748,5106,6435,32,9552,384,8845,5493,6453,9702,4836,3249,1434,1634,3241,7935,7674,2734,2128,6636,3876,2490,6144,5024,8575,4611,7530,7601,1831,7711,2249,6626,1416,8524,5651,7365,7007,7160,2859,2977,4496,4532,1616,7209,7270,7450,3801,3383,4322,1885,6086,1356,1673,4011,5381,8867,8914,7687,5961,7263,5621,8155,4889,9167,8052,1170,8463,5362,1152,9216,4220,9688,4161,9531,1612,638,3456,4951,7370,3567,8061,4852,1600,5540,966,1683,5161,4123,8497,1481,9618,6575,5950,2974,9505,4326,1241,7525,3651,9220,1453,2001,1342,2740,2269,2501,7111,4366,2839,8836,6885,6121,9518,3243,6017,9490,6945,9704,9169,5620,5866,6800,4606,7,4746,2184,8825,8802,9946,5843,3675,835,7150,7888,2527,9186,8418,5406,3717,6041,4132,9620,8157,4252,6415,7838,2395,3993,9774,8788,7103,8178,4894,1659,2384,6744,3825,7203,95,592,3773,497,6397,921,6002,931,564,9337,8292,3115,139,4765,1579,5086,1505,1939,2965,6624,5149,2427,7467,3335,4363,5091,8732,5069,6460,8091,9463,678,9095,7522,8221,8981,6320,2311,2075,5769,3949,9653,9696,8084,4703,8174,4433,488,1654,9875,179,63,4370,5439,174,7076,2036,1186,3186,7507,8474,7979,1263,5307,5380,3277,9225,8440,9753,6871,1856,3724,5873,1159,3452,9084,8921,828,7138,795,226,4401,7417,9222,1991,1343,9837,8571,2611,3393,9873,6877,7890,5625,6919,429,135,1367,4892,815,8535,4016,5840,5949,6523,3413,7638,2156,7816,9093,4705,4959,4821,7710,4585,1671,9140,5639,9258,4748,7476,3854,3905,4284,2085,2841,7176,4031,2754,2642,9091,6729,4866,69,6630,271,7967,3399,2344,4136,4547,9806,4368,2011,8171,558,7768,4493,9850,4417,565,6524,1596,1923,3415,7401,6739,5615,6457,9482,9609,6839,3507,9706,5761,3631,6205,5150,4891,7746,1719,1971,330,4737,4505,3723,5315,8388,9970,6286,2652,6558,8798,9262,4068,68,7153,476,8010,3653,809,8425,960,3669,4381,4462,8414,4835,4423,2568,9264,5282,8170,8395,6316,3071,7499,1639,6968,2524,405,2033,7731,6228,4488,8558,800,2163,6633,7127,1969,8466,4988,1907,238,816,2038,1981,1298,2334,3767,6083,4849,2530,2154,6716,6216,2737,1340,3923,8322,6197,5326,4602,6695,9985,3312,5689,3565,5963,4689,4047,5938,6217,8447,5977,9282,1643,1475,6875,534,2102,1491,6354,6438,7174,1121,6549,9731,358,8747,8910,636,8652,3754,5677,5996,340,5936,9739,9277,6656,1738,8432,1112,3911,2657,7712,4833,6022,8368,8523,4369,8987,7951,7581,5692,9840,7886,848,5358,9786,1739,6451,8087,9189,2400,6420,5235,7728,965,6897,830,4120,4239,453,1362,8928,1938,5970,8950,4675,3108,8297,9766,5238,3450,9938,1928,9993,4979,8686,1826,5685,9403,8192,9711,7767,5696,4740,5337,1903,1015,9560,5556,3424,5268,7899,3950,8831,5704,3533,3735,4088,6774,9238,9485,6268,3330,8960,9780,6931,6590,4555,2120,585,9790,1221,1558,5324,9521,2349,2007,9754,1948,1194,2379,1536,6817,4444,5189,9199,3838,5715,719,5318,6808,1107,9971,3039,9896,4067,1932,764,4186,5906,4187,5248,7585,9204,4650,9417,323,3642,91,884,8650,9784,9625,7102,9237,2125,575,5111,2381,3796,9539,9579,3142,925,5922,8255,9781,4317,7773,628,4170,954,2913,7524,149,5546,2006,9992,6323,4029,5792,6206,2572,6825,8746,903,996,418,3101,583,2724,7413,3329,7077,3866,1346,1289,7533,7019,2548,2004,7093,948,3201,3318,401,7550,551,9793,9217,9717,1519,6697,5357,7366,7027,8664,7308,5205,3203,1440,9941,8391,544,5940,5187,5043,8378,7134,8863,1441,6614,8129,202,1065,5356,8815,9565,7469,3380,1196,1462,9626,5524,5632,2489,6082,9890,5708,4236,7629,9331,6557,1858,3996,4053,6437,6906,6960,1203,1547,5173,8335,4860,4472,48,526,9872,6552,1104,2536,889,8781,7667,850,2235,2081,2801,9421,4576,2851,2090,8363,5391,5765,9506,1677,6108,1811,1700,7011,9014,6222,274,2475,851,8666,1559,2577,9196,4542,1814,3834,3820,3384,9160,8399,9859,4716,9226,4477,2265,8500,6157,7968,6464,5088,3124,7402,7925,9447,9555,5529,5643,3739,5788,7862,590,709,465,7168,7235,3386,3713,7232,7661,5521,1900,2781,4812,746,8288,7295,5240,2891,1108,9341,1404,571,3658,3165,8994,1813,6330,9487,4138,4023,8460,7919,2826,9367,7264,3112,3693,7315,4649,3683,7373,4394,7999,4942,2967,1703,767,8345,9111,4839,9172,2926,3414,2434,245,552,6566,7595,4809,5878,6814,7456,3340,3293,4312,5049,7812,7914,3076,7501,4456,870,7388,4468,9660,3803,7987,6101,880,6511,2450,8975,7202,2771,2074,1306,7152,627,7110,6351,1432,5681,4172,1892,3116,6444,5264,823,6249,4688,9368,2324,6134,5722,8625,2405,6210,559,7079,7851,6037,1625,6585,6742,4494,5065,7429,3504,1243,9270,9497,784,3662,5796,6414,1552,2135,5360,365,6838,735,4014,1609,2945,2674,8549,8151,4741,2446,3721,7829,6546,895,4183,3333,2953,1409,7742,2165,3444,5389,1451,1507,765,4225,8774,7057,1675,9373,9295,782,1880,9058,3045,1379,6491,4616,8740,9239,9414,1158,9996,6029,2396,2484,3714,7708,5678,6730,4625,527,7092,8773,8296,4862,7632,3811,7997,8041,8903,3036,74,8053,3007,8983,8794,6632,736,3947,2239,7671,4867,6857,923,9029,8889,9909,3064,4149,6700,2348,1018,6725,1822,5008,1067,5592,8554,5622,5492,5516,8517,8230,1728,3367,8891,2638,143,8854,653,677,6505,6232,8022,968,9001,8606,643,3057,5343,9692,1329,1684,5929,2768,873,3190,3239,4665,7155,1029,4365,3417,8054,9607,8749,3520,6688,8777,6952,6503,8101,4986,1466,4676,1187,6777,6176,6318,3434,2146,7017,3617,728,2310,5310,2950,2103,3012,7818,3560,5025,803,8037,9252,1944,3969,1333,1294,4203,5270,2979,1838,8647,8563,1798,3980,5500,7314,5901,265,7652,3049,8864,8491,318,8653,7022,712,240,8086,5325,5806,912,6072,1911,6307,4994,2603,5165,7291,3601,6264,7936,2250,489,8548,6040,4279,361,644,8373,5062,6424,5100,1287,2474,3636,3729,7187,2939,7181,1595,8096,1265,8488,7096,7565,3890,6531,5403,3467,5295,4054,5512,6489,5912,2889,6972,5959,1069,5271,2318,1632,3765,3982,8640,4843,5454,2821,8764,283,4222,7449,8654,730,9147,3752,5345,1176,8002,438,6771,8620,1325,8379,8103,6592,7892,7669,3657,5218,1514,5710,4113,7986,4179,899,7828,740,7207,4258,6509,8995,3846,6856,6196,2976,9362,4594,8719,6528,1933,1767,3522,9326,6120,3472,3942,4086,8030,7924,9131,6561,2971,5921,9483,4857,8445,8695,1878,5408,9088,3523,1141,8427,3877,6811,3054,8323,1825,9113,4002,6296,2447,4338,1205,2584,3342,2817,4944,5908,4079,2328,217,9778,9757,3477,7734,771,6670,5744,7205,3837,8507,7403,6618,4696,950,6943,3136,2764,9208,7990,5214,3776,7813,2352,1072,9920,7503,3331,9121,1301,4190,8211,369,7580,8883,8225,2439,2436,4017,7322,3531,2639,4618,3292,3037,637,111,7333,6586,7511,4416,8855,718,7563,9235,542,8075,4810,7005,7132,4514,2140,293,8677,4769,3561,8065,9590,1757,5777,1336,7861,7439,8117,6833,8480,6559,1025,2245,3140,2686,3172,6390,9476,349,4762,1127,8990,2413,2057,5256,1952,3388,7803,788,1495,8675,6382,6577,4700,626,4813,566,7696,9937,7377,4568,4078,8340,53,6514,5563,7723,2526,5753,3539,5724,4201,2228,6971,2576,4116,1949,2094,8958,713,9943,3149,2988,6751,6262,7266,8850,762,7896,6349,8285,8498,3230,3513,8753,6673,395,2158,6242,7809,8581,2739,2818,5027,2106,5245,892,1169,258,6890,2643,3449,1597,744,8954,7677,4771,3219,769,6946,230,2092,6255,6718,8193,4644,5316,1548,1415,6947,5211,2678,5762,5545,4548,1118,2825,8978,7225,9860,449,8725,6851,8351,4426,698,1094,2069,775,5864,8123,734,431,4004,6028,9274,2322,8143,5869,9828,4001,1587,4995,2183,1686,4528,7778,6967,1145,2170,4152,9092,9395,4921,7801,3478,2776,2871,5778,729,5044,8712,8646,3962,6690,794,1177,2123,9556,7685,5701,9072,1113,7287,5394,2104,1812,5181,421,3536,4065,9253,2665,6873,4622,4460,8305,3321,9036,1061,445,9740,801,6959,2516,5508,3040,8197,2387,6598,4479,9564,1444,71,5839,6343,3251,1918,495,9628,4171,5539,6954,4699,4896,3494,6996,3873,1050,9477,9750,1986,8795,6149,284,7721,5085,8111,7446,8016,6155,1631,6534,8140,8726,8716,4798,7210,9910,1239,1457,926,6291,4454,2437,4948,478,8269,5339,8680,887,6102,1722,9815,5725,1737,989,8026,7296,569,7177,8967,440,6609,8371,1167,6484,7939,4902,3512,5063,3857,8412,9507,2886,5619,3527,7038,9935,468,5474,4045,6510,290,232,7678,3170,7668,9844,9865,4478,5577,2892,155,8685,6605,9246,3856,6350,4242,9924,943,2272,1962,577,130,852,9783,3863,3365,3861,7364,1046,1085,5815,8365,9372,1437,937,3748,9193,4975,8800,3935,1257,8044,8742,8328,2295,4356,2872,1976,5023,8369,1227,8262,6728,2300,2168,812,1945,3888,4960,8702,8658,8423,5082,9566,4467,2630,7399,8470,578,6504,6874,8076,7664,9224,8866,7460,4998,8139,8112,9298,4572,3702,1208,6485,9275,4013,5478,9517,9394,6452,6127,5554,6813,8727,8856,6798,6409,6129,8597,1254,2152,1308,1465,2002,6938,7931,5854,4448,3672,9064,3666,9603,5926,6312,4027,3139,9839,7463,3583,26,1873,7451,5990,4141,3648,3073,6450,5479,8949,5278,1258,1887,8152,5393,4645,5597,4482,3814,377,3043,4783,1775,2884,3847,5553,8527,7368,2618,1779,8623,4396,2762,1218,4733,9868,973,6721,599,833,3316,8679,5144,4015,6651,635,4073,5015,2341,6762,2438,4459,7794,785,9557,1661,1136,3722,5313,344,6707,3356,8617,3521,8127,1224,8465,3587,2567,5301,6912,6117,6462,7354,1723,1664,4059,933,720,6646,6796,9135,2037,655,610,2607,2506,1111,7338,6492,3585,6628,7037,4797,1517,1874,1350,144,4729,7498,3364,3535,331,464,8093,392,9545,7009,1429,4895,153,3447,1090,5767,1116,7051,2845,3145,9788,4202,701,8121,9194,4878,3269,9232,8135,6649,2951,3410,9437,2653,2761,8114,2067,4872,5953,9547,9129,9928,6304,6803,9366,1652,7321,2805,5893,9820,3013,7639,1188,4269,1581,2842,605,1410,5136,5376,4383,3921,8329,1164,7278,1251,9278,4617,3623,4795,4340,8838,7100,574,9177,3654,8916,4292,8833,6092,2869,6432,6247,9929,3810,9151,6077,9383,252,4208,224,3210,8017,8676,2355,4072,1133,9842,4205,9045,7583,4077,7023,8735,5813,7921,5837,7995,9663,9343,1334,123,3898,9244,3559,7224,8608,3831,1197,6625,4178,7623,1321,6699,8783,4661,5411,9489,9969,6270,5311,6187,7909,3985,4757,9795,7284,5174,1106,9748,9475,1217,5275,7381,7561,9468,7540,1490,8389,6648,8356,6113,4062,5446,7090,4735,19,1883,6797,141,6908,5781,9735,7694,587,1718,7640,7643,100,7406,2225,5093,3002,2390,9338,9589,7229,8886,4142,779,6654,2946,3363,640,1804,1016,8107,8922,5365,987,8793,6750,2240,3659,1638,596,5242,7375,1862,4874,2072,5424,3235,272,6795,1041,3261,7683,7800,8245,8353,1008,2861,2557,8358,4710,8853,7243,5471,5162,2854,3756,619,6360,285,5117,8475,1843,9751,7490,9163,3366,3072,4323,8982,8040,7326,8976,4227,5898,5948,2115,9975,9905,8401,2084,770,8665,1520,6500,9957,2707,6449,7094,4721,3994,1452,7118,9293,7485,8530,5261,9382,8429,2993,4601,1756,6433,4474,2416,1279,1426,1146,3611,5999,7716,4522,4962,2326,3314,4658,2834,3351,5142,8381,7300,2410,4577,9668,3895,7431,6993,9397,808,971,4901,2994,6581,9138,7887,4163,6843,3266,6279,2838,1628,9870,3704,6884,7551,8334,9191,2223,1019,9713,6178,8586,1919,4273,1866,4261,6051,1074,1742,6705,7884,9855,4257,6693,4464,2417,8759,5186,6133,7233,8943,3416,6085,3832,175,3403,2672,9300,5373,8058,7545,5841,7918,6027,1232,7760,8309,4853,4646,4970,3975,5183,2061,7441,3800,6686,1544,1487,82,9664,5296,5193,6329,2079,1847,7626,2533,2617,6324,3435,9419,2860,1436,1783,8927,3917,5030,3232,6244,7265,2244,9139,9528,5825,9736,8637,8206,8589,7067,7654,5312,8413,3217,7121,4125,6685,2287,6623,1053,55,8359,7258,9069,5118,3829,2005,2873,6456,9219,200,6070,5155,4966,3519,8274,7215,9635,7183,7356,2912,372,2798,7015,2666,5823,6540,7784,9060,4071,15,7297,7457,6929,2972,2785,5305,4535,761,6653,763,9729,4609,649,7787,6165,1304,4605,7335,4150,1244,9782,3147,1655,5234,6601,251,7762,5865,3299,902,9077,3302,5217,7470,5102,7240,5382,2252,4274,424,124,2495,1403,4626,8758,546,3879,3103,8814,1808,606,5709,428,9133,1924,322,3848,9031,4315,9829,6225,6234,337,5599,1574,8766,1953,9592,9040,1476,7727,8422,3428,755,6634,1855,3278,6224,8913,1901,8420,4678,6927,5578,1468,3716,7648,6404,79,9276,7836,6034,7537,8138,1207,2129,3084,8168,6422,8879,6597,4755,4110,3647,6239,4033,9649,2915,7611,2426,199,6608,5797,7538,9511,9646,6258,4247,9785,7472,5349,881,9112,234,2987,9050,1161,8698,7024,2149,9648,5707,5994,2080,3726,858,5249,8024,6068,9452,9615,2233,8110,3667,3297,4709,5776,6116,2481,1312,6259,3700,433,4781,24,3499,1950,6563,1384,8862,6767,5363,5874,7745,9817,8261,4598,935,7913,4885,929,3632,122,732,9408,8448,4967,3491,1564,6804,2393,2863,2055,8489,3188,62,2589,6054,2035,4069,1478,647,7707,2325,5875,75,2755,389,7650,1288,8682,8920,9187,1375,3175,603,7327,3656,2864,8160,3899,1606,7396,7154,1446,3253,8904,6241,306,1689,5482,9986,5252,7874,3902,1368,4413,4199,2660,7917,98,6263,6416,6794,8519,4169,6240,7631,287,2133,2921,9529,1545,2778,2472,2991,2476,1349,9240,9826,5667,7044,348,6100,4035,657,6333,2655,5236,1052,7596,4008,2151,5241,5386,1038,7637,6359,7484,9991,5368,1705,5789,4490,4936,1617,192,7389,7510,2370,8638,8878,4375,9666,9479,2257,1506,9233,6792,7557,8940,9039,6123,4455,4732,7271,7071,41,4305,7518,6596,1845,4347,6809,7433,4518,8181,4773,8326,3686,3081,1955,8632,5518,5895,2963,2316,8347,1771,6997,6984,7732,8068,3056,741,3078,714,5262,2823,7881,2066,3680,9257,919,5691,2911,2640,748,5567,2219,5375,8968,982,6662,5568,7770,1393,6541,9732,5966,6747,128,9502,1565,662,2875,1726,133,8008,2026,8544,9335,6816,5645,7679,941,1566,9598,3379,8627,2157,191,9962,2952,4714,5436,3915,9602,5392,1881,8641,2298,4929,4834,9644,1382,4666,1925,9078,7897,5868,7192,1471,9087,5676,5802,9076,7681,4830,2185,4686,9059,1427,6195,1216,2736,7245,2816,96,9038,3311,6175,1746,5668,1459,9722,9333,9043,9154,1687,8409,686,3840,4854,1537,4876,7462,399,2612,5888,1651,3301,8655,4130,5458,442,9141,6448,6095,1281,7089,4294,6562,568,7743,6860,4500,3954,8227,7489,7494,3555,6631,9995,7430,5544,7269,1472,1729,2356,2171,3566,7084,8339,5565,1162,749,5247,9981,1731,3710,9534,3689,2032,8538,5726,8804,8042,2906,9533,9108,5442,4357,1802,917,4924,7241,664,6160,2025,3360,5711,7926,4987,1026,2968,7337,7751,4372,3229,3346,8763,3612,3556,1853,608,7676,2058,9500,7866,7397,9979,6184,9966,4348,525,5005,2895,3881,7384,4691,6544,2833,4899,3692,2019,680,3348,9952,3087,8669,1307,4530,6280,8162,4402,5092,8319,6130,7310,8984,8275,9532,6183,5918,9816,7367,7216,6548,1394,9249,4905,6202,6192,6754,479,6903,6978,9799,3207,8562,869,8088,5732,1344,6732,8300,9546,8787,5216,6789,9762,5932,893,298,4386,3755,7194,7971,7776,3862,5422,7625,939,2846,3914,9243,6990,916,2984,2673,3509,1009,3280,3206,4976,4302,9184,777,9597,584,5675,9499,3600,666,1119,4378,630,2339,7395,2555,9610,7386,3808,7282,4502,5409,485,2849,2445,8734,2763,9801,9588,9426,5614,4422,3022,1800,5283,7900,6847,2948,4573,5682,4418,8541,7164,8639,829,8217,1326,811,2323,5170,1836,8846,2914,9319,6434,838,3580,8333,5447,7086,1785,6525,57,3017,3937,8495,2807,1554,2773,6593,5457,2338,1098,1580,5050,5497,211,212,9726,9034,6663,531,9568,733,5060,9010,7369,8484,9384,4898,5845,4309,9973,5609,4099,1624,6532,4779,6375,1271,4629,7855,6616,3605,6093,5195,1817,1768,4759,4159,6317,920,5947,8959,8999,3104,4672,270,2704,9478,535,8080,334,1630,1290,2486,8839,8077,2545,370,1623,3677,5799,9519,4580,1799,1338,6849,2364,2313,7697,9827,3135,2425,4339,4250,397,8278,1042,9904,4124,4937,9156,7941,5317,8865,2483,7060,5605,2857,3540,5665,6009,593,3300,2398,6026,818,3579,2221,8709,5980,5718,6617,4880,9271,2623,6158,2210,2743,4055,2547,6845,1299,5757,9100,304,7796,8350,7904,9652,1034,3517,5328,7113,9526,4579,2308,9464,5738,4238,7534,2259,3988,8803,671,8257,2525,6293,2193,35,8587,2597,242,3119,7817,311,9321,4662,1694,64,8602,6342,3544,6311,2728,3481,1400,43,6494,4983,2155,9297,2487,4816,8069,8769,5695,3851,6998,4882,8361,2738,9102,7624,9480,3874,6463,3501,2941,4760,7943,3236,7797,6560,1879,5055,7390,8228,469,5647,6682,6757,1736,6869,1886,9013,1557,2636,1150,7175,4185,9441,4267,7208,4111,1889,8533,7948,896,3193,8046,9165,4277,8299,7730,9846,6356,4793,6569,1140,2521,1551,136,3431,7165,4925,1528,9037,7109,5988,5727,1448,8992,5570,3959,2040,3515,1936,1821,2629,3805,1803,9907,6760,3033,6099,5299,821,7159,3990,3440,9357,1575,1622,3867,3197,4538,7647,5504,2604,8405,5830,1137,7969,2101,2253,1070,3322,2469,1508,231,3173,7858,6832,5705,359,7901,2752,9893,7929,4673,3349,9254,9857,2990,6137,4167,3650,2275,4982,8736,8318,7059,6142,66,7047,5304,2831,6538,5207,2076,2897,2134,1744,3282,5146,73,3762,2685,6227,4774,7542,3166,6378,2059,8612,3465,9352,8477,3480,8407,9948,9212,9745,1364,1795,5251,1357,1066,998,5834,342,2793,3130,517,7171,8384,9118,8905,1120,9494,9049,3164,7147,9586,7536,3734,7347,8004,3928,2701,2956,5058,1934,6119,4492,8779,2020,6944,5800,1498,9548,5302,5281,5001,4521,9689,1455,5591,2,7619,9911,2559,2622,3192,2893,5931,9600,9304,6812,9273,1054,5811,1275,2658,667,8687,4192,7898,1366,5103,110,5384,4707,4346,7344,8704,6519,8348,4100,8899,2799,9287,6278,8902,2550,9821,4266,9832,3671,187,21,2802,2248,2276,374,7961,9223,598,2099,3407,70,8250,241,2420,5611,9375,5897,221,7636,1123,8885,3979,9767,4221,7061,6032,3083,9346,4080,9661,2462,3463,7737,2291,3630,4582,6111,6115,8148,6619,9182,243,5505,6862,3701,8354,4254,5733,1518,999,1693,2986,8253,4985,6091,9503,4634,6156,8169,7078,7966,2321,2883,3594,597,9642,7316,4566,3184,4012,7434,9705,7956,4114,294,3771,9772,6763,6172,8572,710,1680,1644,9777,2451,4904,5962,9021,2874,6219,2467,9897,8622,7139,6676,267,3454,4431,7437,4278,6057,6607,967,7839,502,846,3548,9760,4066,2532,7589,1735,842,9522,6110,1138,5107,8826,4126,4744,7357,1852,114,3189,5385,7876,9632,4200,6822,799,670,9401,228,543,1656,7237,9183,5955,4785,9516,2529,1543,4287,8805,4133,8095,9327,5867,7774,4507,8120,6153,2431,4558,4095,2832,2586,2943,990,2538,5006,8877,1059,8588,2391,9630,8917,3797,2706,5574,5780,1282,3374,922,6520,7289,7095,2837,2882,3123,8754,7864,4048,4441,7145,5537,9510,2222,8074,6920,4285,3433,7508,6629,7856,9956,3429,5952,2633,6325,0,5267,6145,2960,9900,8797,7261,1572,4930,6252,2508,949,5728,2867,1584,3287,9631,255,758,9283,31,4469,5971,9508,45,5209,7715,4653,6208,8906,9803,3502,5237,89,5137,9202,5188,4828,9241,3339,7820,1750,3849,2741,7692,2441,5976,2422,4731,2008,4387,4829,6477,8944,8938,9406,6454,2053,3006,3453,463,6336,8459,8385,5347,4772,8001,8786,9085,1773,4412,8360,4886,6899,6475,1286,6005,7946,3884,1317,4310,7845,6071,9242,8154,8830,3495,6951,8876,1626,9030,3067,3233,8610,5534,1993,6766,4032,3894,7558,3035,4333,3029,1274,2583,4861,7423,4614,1296,2722,7529,1352,329,7600,3224,6684,6888,7994,5428,8342,5775,8137,4965,6047,5306,9520,7859,2127,508,1777,8851,721,3225,813,3375,753,1051,168,7223,7706,7799,7464,7144,550,3725,5140,3606,8125,4752,6396,9611,366,7108,1782,9380,7035,2933,2847,4151,6772,6080,9591,7577,8473,1809,1555,4074,1877,6038,9898,6377,8312,295,2456,5729,2043,7993,3059,3028,3553,7822,367,4964,7142,4915,5338,3419,4552,944,49,6056,855,5463,717,6442,4289,4992,3638,5308,6956,5910,1710,665,7432,1758,7944,5848,7036,6621,2828,4165,8018,9035,993,8048,883,4881,8433,5791,860,7379,7725,317,7318,268,2670,4092,3167,4449,2246,1529,9322,2654,5089,6212,9028,7665,5370,1818,4354,4654,7274,986,5213,1479,6861,2626,2192,2671,4778,9677,3268,7663,2667,6898,6169,6878,5009,6105,3156,412,2361,7942,3086,7670,1702,1418,5656,2573,1305,8991,3069,5335,2513,327,5220,9913,6672,2046,9741,3394,7873,7006,8372,7363,5514,1526,1097,6078,3405,7483,99,9377,1278,90,8730,4010,7128,4131,4712,4176,1206,7163,8957,5808,6385,4475,4933,6355,5000,320,1489,2544,9227,2030,9569,3263,7578,9849,5746,341,4846,7789,6785,3616,6953,5119,5680,2720,3728,612,6319,7579,5731,3676,3111,219,4197,8009,3133,9721,8216,8618,4574,7989,745,511,1193,2505,5351,169,3738,8770,3613,7149,5658,2756,814,2549,1679,8731,2509,107,1963,7805,3275,7840,5412,4685,4233,6362,9097,5650,834,9336,9852,316,7312,2466,5201,9683,9725,5985,4364,1001,5336,9358,4562,2900,5793,7068,5184,3196,1515,7325,423,5610,7980,4021,5772,112,5131,7166,2270,432,8979,2237,3768,7021,6599,2254,2578,462,1166,167,2931,654,1922,302,3460,7285,2256,9205,3432,9026,3089,8029,9997,9719,7030,1377,7376,955,8532,9461,8819,704,1389,4950,9833,6913,8996,1882,6049,5807,8642,6840,9211,6281,9301,9881,9350,5669,8073,2403,6687,716,1930,8254,7186,9083,1604,5774,4243,9125,3127,3674,8204,9370,6387,3500,1714,3618,6731,2358,6779,2777,2141,5404,7135,1635,1570,907,435,4543,8935,9544,4399,7747,1833,7689,537,2114,9906,1772,6902,8557,1743,8690,4890,5133,4295,3524,8672,602,8515,6867,7123,4991,1960,658,5580,1741,7641,6872,1754,9066,9019,7605,2083,1496,5699,3791,7614,9378,7014,9374,3633,5756,5583,4476,8894,9922,6059,797,7355,538,7428,7346,6087,522,3708,4549,6236,8481,8750,7603,6969,1413,2575,3218,886,5562,5197,9936,832,5078,6334,7425,3132,6950,6858,7217,3462,8246,6046,7590,8884,9435,555,6379,7013,4893,1084,3981,1599,6642,2461,3408,5115,2186,6940,8713,3900,3896,3455,4181,792,2748,447,4358,9309,7895,7857,6667,4636,4761,1530,4427,7554,6128,299,7572,648,9268,6635,4039,5330,2868,4218,4637,467,8824,7672,8281,3442,4980,8081,6752,8674,5277,8635,81,39,872,618,8573,3919,5892,3021,706,961,8130,3305,4597,4749,6339,8177,7937,1132,1698,6696,8490,4879,3514,2296,2757,9885,4311,7074,9608,1914,1245,7307,6470,9145,2683,1388,3684,9651,2543,953,5416,2696,7213,2596,280,8390,6455,888,5182,6527,8897,8744,5444,6863,5995,3761,4109,882,9306,897,8821,8273,2881,282,2260,4336,3289,7188,4146,8812,8887,4020,601,910,6052,908,661,2637,3237,1100,1692,1985,4501,6401,825,4207,3291,1058,7414,1603,9247,2097,5191,4485,9951,9624,2051,3573,2855,6852,7420,5613,2138,443,5309,4025,4587,5997,3254,8007,2593,8364,9171,8310,6918,8601,1013,1534,7659,994,9143,6315,3402,5057,1869,9266,7062,8898,2562,4877,1414,4405,2401,5314,9363,553,4972,5066,3784,5925,5108,5064,9033,974,3904,2116,5661,6417,5739,8755,3604,6201,2909,396,7065,8025,3833,4825,472,2553,9727,94,4698,163,1201,4060,2705,3634,9779,9650,1994,3602,5297,4506,6529,223,5348,1313,1083,9146,9847,7922,9462,2047,2682,1438,25,1421,5666,2145,5855,6572,275,2340,446,8179,1797,2399,6043,3392,2333,9089,8844,6257,2227,7690,906,6428,9134,9048,142,7475,9158,4917,9431,6185,6901,4264,5383,645,3668,3401,3742,5081,3097,8801,1721,8534,8200,4219,2050,4557,1309,9234,2937,6231,7566,1109,5817,9538,8055,7984,3743,7868,7041,1473,2750,6850,7515,4480,4043,7945,1688,7253,9081,296,7418,4400,1697,3430,9761,1035,1906,2000,1716,8259,620,3526,1103,5450,5243,3085,5517,1727,8031,4419,2109,9415,3772,7506,2195,7633,5495,2788,8576,7627,2585,22,4325,4355,853,2177,4390,2999,7411,4429,1713,5604,6441,6554,4801,5260,2363,1747,8619,6818,9032,150,8124,9051,2273,2964,6073,4486,335,9563,5046,2599,5664,3924,3570,6893,7852,6479,3211,362,4409,425,430,690,5141,3298,9787,2175,2698,454,6497,5831,3446,6926,8272,8167,6036,6826,6782,9930,5653,3828,4411,3809,1088,2188,5293,9958,9562,8988,5942,1130,6734,3699,8393,6150,1237,5648,2708,5080,4046,7649,2905,1226,6364,5536,9128,5974,2394,3640,3255,6665,663,3015,9537,6103,6904,3971,4947,3438,3285,5671,547,1970,487,4313,6473,2628,3306,5581,9469,6405,23,7651,8105,394,904,6384,184,2421,7161,8717,938,9314,5110,4655,4844,9989,9303,9949,1567,7592,8570,4191,5944,8097,4711,7018,9967,8790,58,7744,6267,7146,5285,5549,2174,9312,556,6243,8032,8872,8104,6207,6802,2668,2367,9601,4599,8332,9959,6335,7560,6965,7905,197,2843,233,1006,3204,1477,2208,2693,876,6139,3252,5274,6332,6535,9168,4822,5012,4301,1202,9703,9596,6118,4118,7197,4251,1904,1778,7158,6964,9636,7832,9862,6740,4838,9308,2644,1302,390,7849,2540,1102,165,6186,409,3093,8156,4764,8456,867,4523,580,934,3920,9245,3095,173,6151,2373,6033,2790,1553,4670,5617,8187,8578,6365,4827,8343,33,2648,1666,3661,4884,7544,7448,7104,5113,5723,4977,1234,2172,8700,4559,3941,8643,1339,6966,2353,9812,373,1749,4174,9265,7073,8158,9342,4084,4569,8871,4718,4359,6493,215,5956,7844,2791,6064,6161,9103,780,1784,9747,393,2289,9578,2560,6859,4763,1463,3610,5,3665,5410,5943,5905,8260,4693,7752,4324,4350,8142,52,691,5486,6122,3182,507,3823,6719,742,134,2601,5885,5449,1681,2814,4841,5828,9558,8175,5660,4715,7156,2908,2283,7806,8239,6230,5642,5053,5244,5602,10000]
result = check_possibility_v2(nums)
print(result)
